package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author By ZengPeng
 */
public class 力扣_106_从中序与后序遍历序列构造二叉树 {
    @Test
    public void main() {
        TreeNode treeNode = buildTree(new int[]{9,3,15,20,7}, new int[]{9,15,7,20,3});
        System.out.println(treeNode);
    }

    /**
    题目：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

     示例 1:
     输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
     输出：[3,9,20,null,null,15,7]

     示例 2:
     输入：inorder = [-1], postorder = [-1]
     输出：[-1]

    分析：【P 💔💔💔】
       1.递归：后续遍历postorder[i]就是顶节点
                中序遍历中找到 inorder[topIndex] == postorder[i],topIndex 左边就是left,右边就是right
                --执行用时：2 ms, 在所有 Java 提交中击败了66.94%的用户
                --时长：25分钟

    边界值 & 注意点：
       1.
     **/
    private Map<Integer,Integer> numbIndex ;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        numbIndex = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++)
            numbIndex.put(inorder[i],i);
        return  dfs(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
    }

    private TreeNode dfs(int[] inorder, int[] postorder, int iStart, int iEnd, int pStart, int pEnd) {
        if(pStart>pEnd) return null;
        TreeNode top = new TreeNode(postorder[pEnd]);
        if(pStart==pEnd) return top;
        int topOfInorderIndex = numbIndex.get(postorder[pEnd]);
        int numb = topOfInorderIndex - iStart ; //得到左子树的元素个数
        top.left = dfs(inorder,postorder,iStart,topOfInorderIndex-1,pStart,pStart+numb-1);
        top.right = dfs(inorder,postorder,topOfInorderIndex+1,iEnd,pStart+numb,pEnd-1);
        return top;
    }
}
